A network processor generally controls the flow of packets between a physical transmission medium, such as a physical layer portion of, e.g., an asynchronous transfer mode (ATM) network or synchronous optical network (SONET), and a switch fabric in a router or other type of packet switch. Such routers and switches generally include multiple network processors, e.g., arranged in the form of an array of line or port cards with one or more of the processors associated with each of the cards.
Packets in the routing and switching context are also commonly referred to as PDUs, and are typically variable in size. However, a switch fabric is often configured to process data only in fixed-size units, commonly referred to as cells. A given PDU received at an ingress line card of a router or switch is therefore processed, under the control of a network processor, to separate it into cells suitable for processing in the switch fabric.
In order to keep track of which cells are associated with which PDUs, a linked list approach is typically used in which head and tail pointers are stored for each PDU being processed. The head pointer identifies in a data buffer the particular block that stores a first cell of the PDU. Similarly, the tail pointer identifies in the data buffer the particular block that stores a final cell of the PDU. The data buffer blocks are typically linked such that an entire PDU as stored in the data buffer is identifiable using only the head and tail pointers.
A conventional network processor typically utilizes a dynamic random access memory (DRAM) to store the linked list data structure. DRAMs are a preferred storage technology for use in conjunction with such network processors, in that DRAMs can provide a large storage capacity at a limited power consumption.
DRAMs within or otherwise associated with a network processor are typically arranged in the form of multiple memory banks. Consecutive read or write accesses to an address or addresses within a given one of the banks will require waiting a random cycle time Trc for completion of a required access pre-charge process. However, consecutive accesses to even the same address within different banks do not experience this Trc wait time, which is also referred to herein as the bank conflict penalty.
Static random access memories (SRAMs) avoid the bank conflict penalty altogether. That is, any address in the memory can be accessed in a fixed time without incurring the Trc wait time associated with DRAMs. The drawback of SRAMS, however, is that their storage capacity is typically an order of magnitude lower, and their power consumption is typically two orders of magnitude higher, relative to comparably-sized DRAMs.
A number of DRAMs known in the art are specifically configured to reduce the Trc wait time described above. For example, a so-called fast cycle DRAM (FCDRAM) is particularly designed to exhibit a minimal Trc. A more particular example of an FCDRAM, commercially available from Toshiba, is identified by part number TC59LM814CFT-50. In this particular type of FCDRAM, the random cycle time Trc is limited to 5T, where T denotes the memory clock period. A memory access, either read or write, requires two clock periods, and maximum data throughput is achieved by using a so-called “four-burst” mode. For example, using a 200 MHz memory clock and an FCDRAM configured in four banks, with each of the banks including 4M memory words of 16 bits each, the memory clock period T is 5 nanoseconds and Trc is 25 nanoseconds, and the maximum data throughput using the four-burst mode is approximately 6.4 Gigabits per second (Gbps). However, if consecutive memory accesses go to the same one of the four banks, the data throughput is reduced to approximately 2.5 Gbps, as a result of the Trc wait time.
U.S. patent application Ser. No. 10/025,331, filed Dec. 19, 2001 and entitled “Dynamic Random Access Memory System with Bank Conflict Avoidance Feature,” which is commonly assigned herewith and incorporated by reference herein, discloses an improved DRAM-based memory architecture, for use in conjunction with a network processor or other processing device, which can provide the storage capacity and low power consumption advantages of DRAMs while also providing the advantage of SRAMs in terms of avoiding the problems associated with the above-described bank conflict penalty.
Despite the considerable advantages provided by the techniques described in the above-cited U.S. patent application Ser. No. 10/025,331, a need remains for further improvements, particularly in the storage, maintenance and other processing of a linked list when using a DRAM which comprises multiple memory banks.
More specifically, in situations in which the network processor is being utilized for high-rate processing of PDUs, memory latencies can increase significantly, to the point that linked list traversal becomes a hardware bottleneck that is further complicated by the inefficiencies commonly associated with DRAM. The conventional approach involving maintenance of a single linked list data structure for a given multi-bank DRAM is therefore problematic, and represents an undue limitation on the throughput performance of the processor.